class ExamRoom
{
    set<int> used;  // 存储已使用的座位
    const int capacity;
public:
    ExamRoom(int n)
        : capacity(n - 1)
    {}
    
    int seat()
    {
        // 如果考场里没有人，那么学生就坐在 0 号座位上
        if(used.empty())
        {
            used.insert(0);
            return 0;
        }

        vector<int> seats = vector(used.begin(), used.end());
        // 这里 distance 是第一个区间的长度
        // 如果第一个位置(0)坐了，那么 distance 就是 0
        // 如果第一个位置(0)没有被坐，那么distance 就是大于 0 的数，代表第一个区间的长度
        int distance = seats[0], finalSeat = 0;
        int n = seats.size();

        for(int i = 1; i < n; i++)
        {
            // 取所有相邻区间计算中点及离左边界的距离
            int mid = (seats[i] + seats[i - 1]) >> 1;
            if(mid - seats[i - 1] > distance)
            {
                finalSeat = mid;
                distance = mid - seats[i - 1];
            }
        }

        // 特殊判断最后一个区间，若最后一个区间的长度大于 distance，那么说明此时应当选择最后一个座位
        if(capacity - seats[n - 1] > distance)
            finalSeat = capacity;
        
        used.insert(finalSeat);
        return finalSeat;
    }
    
    void leave(int p)
    {
        // 保证有学生正坐在座位 p 上
        used.erase(p);      
    }
};

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom* obj = new ExamRoom(n);
 * int param_1 = obj->seat();
 * obj->leave(p);
 */